#include <iostream>
using namespace std;

const int N=1005;
int v[N], w[N];
int f01[N][N];  //朴素01背包
int ff01[N];    //一维优化01背包
int f[N];       //完全背包

int main(){
    int n,m; cin>>n>>m;
    for(int i=0;i<n;++i)cin>>v[i]>>w[i];

    // 朴素01背包
    for(int i=0;i<n;++i)
        for(int j=0;j<=m;j++){
            f01[i][j] = f01[i-1][j];    //不选第i个物品
            if(j>=v[i]) f01[i][j] = max(f01[i][j], f01[i-1][j-v[i]]+w[i]);
        }

    // 一维优化01背包
    for(int i=0;i<n;++i)
        for(int j=m;j>=v[i];--j)
            ff01[j] = max(ff01[j], ff01[j-v[i]]+w[i]); 

    // 一维完全背包
    for(int i=0;i<n;++i)
        for(int j=v[i];j<=m;++j)
            f[j] = max(f[j], f[j-v[i]]+w[i]);            
   return 0;
}